The present inventions are related to systems and methods for performing branch prediction in a processing system, and more particularly to change of flow prediction processing.
A processing system generally executes instructions accessed from a computer readable medium. In a simplistic system, the instructions are stored in their order of execution allowing for pre-fetching the next instruction to be executed concurrent with execution of a current instruction. Such pre-fetching dramatically improves performance in a pipelined processing system.
The aforementioned performance increase is limited in more complex systems where non-sequential instructions are utilized. Where such non-sequential instructions are used, the next instruction to be executed is not necessarily the next instruction in sequence, but rather is determined based upon the result of executing the prior instruction. Where the result indicates a branch to other than the next sequential instruction, nullification of at least some pre-fetched instructions once the preceding instruction concludes is required. Such nullification results in a performance penalty where the next instruction to be executed is introduced to the pipeline only after the preceding instruction concludes. The severity of the performance penalty depends upon the percentage of times that a pre-fetched instruction must be nullified and the depth of any pipeline that must be flushed whenever a nullification is required. Some systems employ branch prediction algorithms that seek to reduce the percentage of nullifications. Such branch prediction algorithms, however, do not account for various changes in program flow and as such incur unnecessary performance penalties.
Hence, for at least the aforementioned reasons, there exists a need in the art for advanced systems and methods for reducing performance penalties associated with change of flow instructions.